package com.liushi.util;

import java.util.*;

/**
 * @ClassName TreeNode
 * @Description LeetCode上所用的树的结构
 * @Author liushi
 * @Date 2020/10/24 10:52
 * @Version V1.0
 **/
public class TreeNode implements Comparable<TreeNode> {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int x) {
        val = x;
    }

    public void preOrderTraverse() {
        System.out.print(this.val + " ");
        if (this.left != null) {
            this.left.preOrderTraverse();
        }
        if (this.right != null) {
            this.right.preOrderTraverse();
        }
    }

    public void infixOrderTraverse() {
        if (this.left != null) {
            this.left.infixOrderTraverse();
        }
        System.out.print(this.val + " ");
        if (this.right != null) {
            this.right.infixOrderTraverse();
        }
    }

    /**
     * 非递归方式, 先序遍历二叉树    头 -> 左 -> 右
     * 1) 弹出就打印
     * 2) 弹出的节点如果有右子树, 先将其右子树压入栈, 没有则不处理
     * 3) 弹出的节点如果有左子树, 后将其左子树压入栈, 没有则不处理
     */
    public void nonRecursivePre(TreeNode head) {
        System.out.println("pre-order: ");
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.add(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.print(head.val + " ");
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }

    /**
     * 非递归方式, 中序遍历二叉树
     * 1) 整个左边界依次入栈
     * 2) 1)情况无法满足, 则弹出并打印, 然后有数继续执行 1)
     */
    public void nonRecursiveInfix(TreeNode head) {
        System.out.println("infix-order: ");
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.print(head.val + " ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }

    /**
     * 非递归方式, 后序遍历二叉树  头 -> 右 -> 左. 逆序 左 -> 右 -> 头
     * 1) 弹出不打印, 而是放入另一个栈中
     * 2) 弹出的节点如果有左子树, 先将其左子树压入栈, 没有则不处理
     * 3) 弹出的节点如果有右子树, 后将其右子树压入栈, 没有则不处理
     * 4) 最后遍历另一个栈, 打印结果
     */
    public void nonRecursivePost(TreeNode head) {
        System.out.println("post-order (use two stack): ");
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> resStack = new Stack<>();
            stack.add(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                resStack.push(head);
                if (head.left != null) {
                    stack.push(head.left);
                }
                if (head.right != null) {
                    stack.push(head.right);
                }
            }
            while (!resStack.isEmpty()) {
                System.out.print(resStack.pop().val + " ");
            }
        }
        System.out.println();
    }

    /**
     * 非递归方式, 使用一个栈后序遍历二叉树
     */
    public void nonRecursivePost02(TreeNode head) {
        System.out.println("post-order (only use one stack): ");
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(head);
            TreeNode c = null;
            while (!stack.isEmpty()) {
                c = stack.peek();
                // 如果左树没有打印处理, 那就先处理左树 (后序: 左 右 中)
                // head != c.right 为什么要多这一个条件呢?
                // 根据后序遍历规则`左 -> 右 -> 中`如果有右边处理完了, 表示左树也是处理完的
                if (c.left != null && head != c.left && head != c.right) {
                    stack.push(c.left);
                    // 如果右树处理没有打印处理, 那在去处理右树
                } else if (c.right != null && head != c.right) {
                    stack.push(c.right);
                } else {
                    // 如果左右子树都处理完了(左右子树都为NULL也算是处理完了)
                    // 那就弹出打印输出, 让head指向c位置
                    System.out.print(stack.pop().val + " ");
                    head = c;
                }
            }
        }
        System.out.println("");
    }

    /**
     * 层次遍历
     * 1) 弹出队列头部 removeFirst(), 并打印
     * 2) 如果弹出的元素有左子树, 将左子树入队列addLast()
     * 3) 如果弹出的元素有右子树, 将右子树入队列addLast()
     */
    public void levelTraverse(TreeNode head) {
        System.out.println("level Traverse: ");
        if (head != null) {
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.push(head);
            while (!queue.isEmpty()) {
                TreeNode cur = queue.removeFirst();
                System.out.print(cur.val + " ");

                if (cur.left != null) {
                    queue.addLast(cur.left);
                }
                if (cur.right != null) {
                    queue.addLast(cur.right);
                }
            }
        }

        System.out.println("");
    }

    /**
     * 求树的最大宽度 -- 使用Map方式, 记录每个节点进队列的层数
     * Tips: 可以通过设置flag变量的方式, 来发现某一层的结束
     * 当前弹出节点所在的层数 与 目前统计层的层数一直, 不需要更新. 当前层宽度++
     */
    public int maxWidthUseMap(TreeNode head) {
        if (head == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(head);
        // key在哪一层
        Map<TreeNode, Integer> map = new HashMap<>(16);
        map.put(head, 1);
        int curLevel = 1;       // 当前你正在统计哪一层的宽度
        // Tips: 这个参数弹出时才统计
        int curLevelNodes = 0;  // 当前层curLevel层, 宽度目前是多少
        int max = 0;            // 宽度的最大值
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            Integer curNodeLevel = map.get(cur);
            if (cur.left != null) {
                // 每个节点进队列时, 把它的层数记号
                map.put(cur.left, curNodeLevel + 1);
                queue.add(cur.left);
            }
            if (cur.right != null) {
                map.put(cur.right, curNodeLevel + 1);
                queue.add(cur.right);
            }

            // 更新层数的统计
            // 当前弹出节点所在层数 == 目前统计的层数一致, 当前层宽度++
            if (curNodeLevel == curLevel) {
                curLevelNodes++;
                // 比较不一致, 说明是新一层的开始了
                // 更新max, curLevel层数++, 当前层宽度初始位为1
            } else {
                max = Math.max(max, curLevelNodes);
                curLevel++;
                curLevelNodes = 1;
            }
        }
        max = Math.max(max, curLevelNodes);

        return max;
    }

    /**
     * 先序方式 序列化二叉树, 将二叉树序列化为一个数组形式
     * 序列化的时候注意null节点也要加进去, 剩余的就是树的递归序处理
     * <p>
     * Tips:  先序/中序/后序的区别就是 ans.add(...) 放的位置不一样
     *
     * @return Queue<String>
     */
    public Queue<String> preSerial(TreeNode head) {
        Queue<String> ans = new LinkedList<>();
        pres(head, ans);
        return ans;
    }

    private void pres(TreeNode head, Queue<String> ans) {
        if (head == null) {
            ans.add(null);
        } else {
            ans.add(String.valueOf(head.val));
            pres(head.left, ans);
            pres(head.right, ans);
        }
    }

    /**
     * 根据一个先序方式序列化的数组, 反序列化出一个二叉树
     * <p>
     * Tips: 反序列化的时候, 遇到了NULL值, 就直接return null; (有返回值)
     * .     而序列化的时候, 则相反, 遇到NULL值, 添加NULL值 (无返回值)
     *
     * @return TreeNode
     */
    public TreeNode buildByPreQueue(Queue<String> preList) {
        if (preList == null || preList.size() == 0) {
            return null;
        }
        return preBuild(preList);
    }

    private TreeNode preBuild(Queue<String> preList) {
        String value = preList.poll();
        if (value == null) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(value));
        node.left = preBuild(preList);
        node.right = preBuild(preList);
        return node;
    }

    /**
     * 按层级遍历方式序列化二叉树
     * <p>
     * Tips: 在层次遍历的时候, 如果为NULL, 就按照NULL存储起来
     * .     不为NULL的节点才会加入queue队列
     */
    public Queue<String> levelSerial(TreeNode head) {
        Queue<String> ans = new LinkedList<>();
        if (head == null) {
            ans.add(null);
        } else {
            // 头节点单独加入队列里面去
            ans.add(String.valueOf(head.val));
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(head);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                // 左孩子不等于NULL, 既序列化, 也加入queue队列
                if (node.left != null) {
                    queue.add(node.left);
                    ans.add(String.valueOf(node.left.val));
                    // 左孩子等于NULL, 只序列化
                } else {
                    ans.add(null);
                }
                if (node.right != null) {
                    queue.add(node.right);
                    ans.add(String.valueOf(node.right.val));
                } else {
                    ans.add(null);
                }
            }
        }
        return ans;
    }

    /**
     * 反序列化出层级遍历序列化的队列结果
     * <p>
     * Tips: 都要建立节点, NULL也要建立节点, 但不为NULL才加队列
     */
    public TreeNode buildByLevelQueue(Queue<String> levelList) {
        if (levelList == null || levelList.size() == 0) {
            return null;
        }
        TreeNode head = generateNode(levelList.poll());
        Queue<TreeNode> queue = new LinkedList<>();
        if (head != null) {
            queue.add(head);
        }
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            node.left = generateNode(levelList.poll());
            node.right = generateNode(levelList.poll());
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return head;
    }

    /**
     * 创建节点, 非空
     */
    public TreeNode generateNode(String val) {
        if (val == null) {
            return null;
        }
        return new TreeNode(Integer.parseInt(val));
        // return val == null ? null : new TreeNode(Integer.parseInt(val));
    }

    /**
     * 添加结点的方法
     * 递归的形式添加结点,注意需要添加二叉排序树要求
     *
     * @param node
     */
    public void addNode(TreeNode node) {
        if (node == null) {
            return;
        }

        // 判断传入的结点的值,和当前子树的跟结点的值关系
        if (this.val > node.val) {
            // 如果当前结点左子树结点为null
            if (this.left == null) {
                this.left = node;
            } else {
                // 递归的向左子树添加
                this.left.addNode(node);
            }
        } else {
            // 添加的结点的值大于或等于当前结点的值,就放在当前结点的右边
            if (this.right == null) {
                // 如果当前结点右子树结点为null
                this.right = node;
            } else {
                // 否则递归的向右子树添加
                this.right.addNode(node);
            }
        }
    }

    /**
     * 查找要删除的结点
     *
     * @param val 希望删除的结点的值
     * @return 如果找到返回该结点, 否则返回null
     */
    public TreeNode search(int val) {
        // 如果找到就是该节点
        if (val == this.val) {
            return this;
            // 如果查找的值小于当前结点,向左子树递归查找
        } else if (val < this.val) {
            // 如果左子节点为空,那么直接返回null
            if (this.left == null) {
                return null;
            }
            return this.left.search(val);
            // 如果查找的值大于或等于当前结点,向左子树递归查找
        } else {
            // 如果右子节点为空,那么直接返回null
            if (this.right == null) {
                return null;
            }
            return this.right.search(val);
        }
    }

    /**
     * 查找要删除结点的父结点
     *
     * @param val 要找到结点的值
     * @return 返回的是要删除的结点的父结点, 如果没有就返回null
     */
    public TreeNode searchParent(int val) {
        // 如果当前结点就是要删除的结点的父结点,就返回
        if ((this.left != null && this.left.val == val)
                || (this.right != null && this.right.val == val)) {
            return this;
        } else {
            // 如果查找的值小于当前结点的值,并且当前结点的左子节点不为空
            if (val < this.val && this.left != null) {
                // 向左子树查找
                return this.left.searchParent(val);
                // 如果查找的值大于或等于当前结点的值,并且当前结点的左子节点不为空
            } else if (val >= this.val && this.right != null) {
                // 向右子树查找
                return this.right.searchParent(val);
            } else {
                // 没有找到父结点,比如删除根节点root,它就是没有父节点的
                return null;
            }
        }
    }

    /**
     * 删除结点
     *
     * @param val
     */
    public void delNode(int val) {
        TreeNode root = this.getRoot();
        if (getRoot() == null) {
            System.out.println("二叉排序树已经为空,不能删除结点!");
            return;
        } else {
            // 1.需要先找到需要删除的节点 targetNode
            TreeNode targetNode = search(val);
            // 如果没有找到要删除的结点
            if (targetNode == null) {
                return;
            }
            // 如果我们发现当前这颗二叉排序树只有一个结点
            if (root.left == null && root.right == null) {
                // 这里无法将本身置空!!!
                root.val = -1;
                return;
            }
            // 去找targetNode的父结点
            TreeNode parent = searchParent(val);

            // 第一种情况：如果要删除的结点是叶子结点
            if (targetNode.right == null && targetNode.left == null) {
                // 判断targetNode是父结点的左子结点，还是右子结点
                // 说明是左子结点
                if (parent.left != null && parent.left.val == targetNode.val) {
                    parent.left = null;
                    // 说明是右子结点
                } else if (parent.right != null && parent.right.val == targetNode.val) {
                    parent.right = null;
                }
                // 第三种情况：删除的结点是有两颗子树的结点
            } else if (targetNode.left != null && targetNode.right != null) {
                // 思路1:从target的右子树找到最小值
//                int minVal = delRightTreeMin(targetNode);
//                targetNode.val = minVal;
                // 思路2:从target的左子树找到最大值
                int maxVal = delLeftTreeMax(targetNode);
                targetNode.val = maxVal;

                // 剩余下面的判断条件就是 就是第二种情况：
                // 如果删除的结点只有一颗子树的结点
            } else {
                // 如果要删除的targetNode结点有左结点
                if (targetNode.left != null) {
                    if (parent != null) {
                        // 如果targetNode是parent的左子结点
                        if (targetNode.val == parent.left.val) {
                            parent.left = targetNode.left;
                        } else {  // 如果targetNode是parent的右子结点
                            parent.right = targetNode.left;
                        }
                    } else {
                        this.setRoot(targetNode.left);
                    }
                    // 如果删除的targetNode结点有右结点
                } else {
                    if (parent != null) {
                        // 如果targetNode是parent的左子结点
                        if (targetNode.val == parent.left.val) {
                            parent.left = targetNode.right;
                        } else { // 如果targetNode是parent的右子结点
                            parent.right = targetNode.right;
                        }
                    } else {
                        this.setRoot(targetNode.right);
                    }
                }
            }

            // 自己的写法
            // 第二种情况，如果删除的结点只有一颗子树的结点
            // targetNode是parent的左子树
            /*if (parent.left != null && parent.left.val == targetNode.val) {
                // 说明是左子结点
                if (targetNode.left != null && targetNode.right == null) {
                    parent.left = targetNode.left;
                } else if (targetNode.right != null && targetNode.left == null) {
                    parent.left = targetNode.right;
                }
                // targetNode是parent的右子树
            } else if (parent.right != null && parent.right.val == targetNode.val) {
                // 说明是右子结点
                if (targetNode.left != null && targetNode.right == null) {
                    parent.right = targetNode.left;
                } else if (targetNode.right != null && targetNode.left == null) {
                    parent.right = targetNode.right;
                }
            }*/
        }
    }

    /**
     * 思路：从target的右子树找到最小值
     * 1.返回的以node为根结点的二叉排序树的最小结点的值
     * 2.删除node为根结点的二叉排序树的最小结点
     *
     * @param node 传入的结点（当做二叉排序树的根节点）
     * @return 返回的以node为根结点的二叉排序树的最小结点的值
     */
    public int delRightTreeMin(TreeNode node) {
        TreeNode target = node.right;

        // 循环的查找左子结点，就会找到最小值，直到结点为空
        while (target.left != null) {
            target = target.left;
        }
        // 循环结束后，这时候target就只指向最小结点，而且这个结点还是一个叶子结点
        // 删除这个最小结点[它是一个叶子结点，可以直接删除]
        delNode(target.val);
        // 返回最小结点的值
        return target.val;
    }

    /**
     * 思路：从target的左子树找到最大值
     * 1.返回的以node为根结点的二叉排序树的最大结点的值
     * 2.删除node为根结点的二叉排序树的最大结点
     *
     * @param node 传入的结点（当做二叉排序树的根节点）
     * @return 返回的以node为根结点的二叉排序树的最大结点的值
     */
    public int delLeftTreeMax(TreeNode node) {
        TreeNode target = node.left;

        // 循环的查找右子结点，就会找到最大值，直到结点为空
        while (target.right != null) {
            target = target.right;
        }
        // 循环结束后，这时候target就指向最大结点，而且这个结点还是一个叶子结点
        // 删除这个最大结点[它是一个叶子结点，可以直接删除]
        delNode(target.val);
        // 返回最大结点的值
        return target.val;
    }

    public TreeNode getRoot() {
        return this;
    }

    public void setRoot(TreeNode node) {
        this.val = node.val;
        this.left = node.left;
        this.right = node.right;
    }


    @Override
    public int compareTo(TreeNode o) {
        // 表示从小到大排序
        return this.val - o.val;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                '}';
    }
}
